package queue_stack.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 小行星碰撞
 * @date 2022/8/12 23:18
 **/
public class OfferII037_AsteroidCollision {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : asteroids) {
            if (num > 0 || stack.isEmpty() || stack.peek() < 0) {
                stack.push(num);
            } else {
                int pop = stack.pop();
                int tmp = pop + num;
                while (tmp < 0 && !stack.isEmpty() && stack.peek() > 0) {
                    pop = stack.pop();
                    tmp = pop + num;
                }
                if (tmp > 0) {
                    stack.push(pop);
                } else if (tmp < 0){
                    stack.push(num);
                }
            }
        }
        int[] res = new int[stack.size()];
        int index = res.length - 1;
        while (!stack.isEmpty()) {
            res[index--] = stack.pop();
        }
        return res;
    }
}
